Alice travels a lot for work. On each trip, she visits one
city before returning home.
Recently, someone asked her: "How many different cities
have you visited for work?" Fortunately, Alice kept a record of all her
trips. Help Alice determine the number of unique cities she has visited at
least once.
Input. The first line contains the number of test cases t (t ≤ 50). The first line of each test case contains the number of
trips n Alice
has taken for work. The following n lines describe the trips: the i-th line contains the name of the
city Alice visited on her i-th trip.
The cities Alice visits have simple names: they contain only
uppercase letters, contain at least one letter, and do not contain spaces.
The number of trips does not exceed 100, and each city name contains no more than 20 characters.
Output. For each test case, print a single number on a new line – the number of unique cities Alice
visited during her work trips.
|
Sample
input |
Sample
output |
|
2 7 saskatoon toronto winnipeg toronto vancouver saskatoon toronto 3 edmonton edmonton edmonton |
4 1 |
data structures – set
Let’s add the names of the
cities from each test case to a set of strings. The number of
visited cities will be equal to the size of this set.
Algorithm realization
Declare a string word and a set of strings s.
string word;
set<string>
s;
Read the number of test cases tests and process each of the tests
sequentially.
cin >> tests;
while(tests--)
{
Read the number of cities n. Clear the set s.
cin >> n;
s.clear();
Read the city names and add them to the set s.
while(n--)
{
cin >> word;
s.insert(word);
}
Print the number of distinct visited cities.
cout << s.size() << endl;
}
Java realization
import java.util.*;
public class Main
{
public static void
main(String[] args)
{
Scanner con = new
Scanner(System.in);
TreeSet<String> s = new
TreeSet<String>();
int tests = con.nextInt();
for(int i = 0;
i < tests; i++)
{
int n = con.nextInt();
s.clear();
for(int j = 0;
j < n; j++)
{
String
word = con.next();
s.add(word);
}
System.out.println(s.size());
}
con.close();
}
}
Python realization
Read the number of test cases tests and process each of the tests
sequentially.
tests = int(input())
for _ in range(tests):
Read the number of cities n. Clear the set s.
n = int(input())
s = set({})
Read the city names and add them to the set s.
for _ in range(n):
s.add(input())
Print the number of distinct visited cities.
print(len(s))